package com.jiang.daily.Q1733;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/09/11 17:26
 */
class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        Set<Integer> nums = new HashSet<>(); // 没有关联的人
        for (int[] fri: friendships) { // 找出没有关联的人
            Map<Integer, Integer> map = new HashMap<>();
            for (int lan: languages[fri[0] - 1]) {
                map.put(lan, 1);
            }
            boolean conn = false;
            for (int lan: languages[fri[1] - 1]) {
                if (map.containsKey(lan)) {
                    conn = true;
                    break;
                }
            }

            if (!conn) {
                nums.add(fri[0] - 1);
                nums.add(fri[1] - 1);
            }
        }

        // 找出没有关联的人中哪种语言是掌握最多的，没有关联的且没掌握的的人数就是最后答案
        int maxCnt = 0;
        int[] cnt = new int[n + 1]; // 用来记录语言的个数
        for (int num: nums) {
            for (int lan: languages[num]) {
                cnt[lan]++;
                maxCnt = Math.max(maxCnt, cnt[lan]);
            }
        }

        return nums.size() - maxCnt;
    }
}
